package sort;

import java.util.Arrays;

public class HeapSort implements MySort {
    public static void main(String[] args) {
        int a[] = {8,9,1,7,2,3,5,4,6,0};
        MySort sort = new HeapSort();
        sort.sort(a);
        System.out.println(Arrays.toString(a));
    }
    @Override
    public void sort(int[] a) {
        for(int i=a.length/2-1;i>=0;i--){
            adjust(a,i,a.length);
        }

        int temp;
        for(int i=a.length;i>0;i--){
            temp = a[i-1];
            a[i-1] = a[0];
            a[0] = temp;
            adjust(a,0,i-1);
        }
    }
    public void adjust(int[] a,int i, int length){
        int temp = a[i];
        for(int k=2*i+1;k<length;k=2*k+1){
            if(k+1<length&&a[k+1]>a[k]){
                k++;
            }
            if(temp<a[k]){
                a[i] = a[k];
                i=k;
            }else {
                break;
            }
        }
        a[i] = temp;
    }
}
